#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstdio>

#define N 10007
#define ll long long
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if (ch=='-') f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}

int n,k,tot,p[N];
ll f[N][30];

bool dfs(int now,int k,int tmp)
{
    if (!k) return tmp==n;
    k--;
    for (;now+k<=tot;now++)
    {
        if (f[now][k]<0) return 0;
        if (f[now][k]*tmp>n) return 0;
        if (dfs(now+1,k,tmp*p[now])) return 1;
    }
    return 0;
}
inline void solve()
{
    n=read();k=read();tot=0;
    for (int i=1;i*i<=n;i++)
        if (n%i==0)
        {
            p[++tot]=i;
            if (i*i!=n) p[++tot]=n/i;
        }
    sort(p+1,p+tot+1);
    for (int i=1;i<=tot;i++)
    {
        ll tmp=1;
        for (int j=0;j<k&&i+j<=tot;f[i][j++]=tmp)
            if (tmp>0)
            {
                tmp*=p[i+j];
                if (tmp>n) tmp=-1;
            }
    }
    if (dfs(1,k,1)) puts("TAK");
    else puts("NIE");
}
int main()
{
    int Case=read();
    while (Case--)
        solve();
}
